There are presently available a number of well-documented techniques devoted to detection, location and correction of errors in binary coded information which is transmitted serially a bit at a time between remote stations. Such transmission is often over an imperfect communications network: ratio telegraphy is subject to atmospheric disturbances, telephony is subject to cross-talk and line noise, gating networks within a data processing computer are subject to spurious oscillations, a computer system involving cooperation between peripheral equipments is subject to intermittent loss of synchronization, etc. Such error handling techniques may be as limited as an odd-even parity check, capable only of detecting an odd or even number of errors, or as potent as burst checking systems capable of correcting a plurality of combinational types of error. In order to provide a background which will serve to distinguish the contribution of the present invention, some of these sytems will be reviewed briefly.
The parity check adds, usually, a check bit to the information bits and all bits are transmitted as a train of signals, each signal representing one bit. For example, for an even parity check, the value of the check bit is chosen so that each transmitted data group comprises an even number of binary 1 bits (i.e., the modulo 2 sum of the data group is computed). On reception of the data group, the presence of an odd sum indicates that an odd number of errors has occurred. This system cannot detect an even number of errors, it cannot indicate the location of errors within the data group and it cannot correct them without calling for the retransmission of the data group.
An advantage of prime significance beyond the above is a system which locates and corrects a single transmission error in a data group by generating ("encoding") and transmitting a plurality of "locator" parity bits which are a function of the bits in selected bit positions of the data group. The selection sequence, for data groups in which locator parity bits follow information bits in transmission, resembles a binary counting sequence and the function is, as with the parity check, the modulo 2 sum. In operation, if a parity check ("decoding") produces a count of 0 for each selection of bits, no error was made, but if the result is otherwise, a combined count comprising all selection counts will indicate the bit position of the data group occupied by the bit in error. This system has been extended to detection of a double error by adding another "error-type" parity bit which checks all bit positions of the data group.
Both single error correction and double error detection are also achieved by selection of bit positions in accordance with a shift sequence; a considerable practical advantage thereof is that mechanization of the parity checks may be by a shift register having an "exclusive OR" feedback connection from one or more of the stages such that the register count recycle. Since more than one cyclic sequence may be generated by registers having at least three stages and this type of feedback connection, it is immaterial which sequence is employed provided that both the encoder at the transmitting station and the decoder at the receiving station use the same one. Further, this approach has been extended to checking errors in other combinations of bits by adding an additional locator parity bit and an additional error-type parity bit. Both the locator and error-type bits are chosen by cyclic sequence selections of bit positions of the data group and thus two sequence generators are required.
It is, of course, known that many other codes may be derived to accomplish the objects of error detection, location and correction. The basis for the high regard attached to cyclic coding and decoding is the simplicity of the circuitry with which they may be mechanized, namely, with shift registers incorporating one or more module 2 or complemented modulo 2 feedback connections, i.e., exclusive "OR" connections.
A typical application of this technique is to the problem of transmission fidelity for a system involving parallel-by-bit, serial-by-character transmission of digital information such as widely found in magnetic tape, punched cards and buffer equipment used for communication with high speed computers, in parallel computers themselves, etc., for which one of the intents of the design is to speed operation by providing a plurality of communications paths operating on a plurality of information simultaneously. Thus, a magnetic tape unit capable of, for instance, 9-channel storage, may have a sensing multiple head which generates 9 bits simultaneously (which together may represent a character), one on each of 9 lines communicating with a computer arithmetic unit; a plurality of characters are generated sequentially and may further be divided into sequences of words, each, usually, comprising the same number of characters.
For this type of system, several techniques have been employed to permit correction of errors in a single channel (such as sensed by the head of a track of a multi-track tape); these generally involved various coding techniques to identify the track having erroneous bits and then a parity track to determine parity over the corresponding bits in all the channels (i.e., the character) and so determine the errors. The coding techniques include cyclic and longitudinal redundancy, residue, diagonal, orthogonal, etc., capable of detecting and correcting many error patterns.
In order to accomplish error checking in a plurality of tracks, these techniques have been extended to generate additional information: pointers (i.e., indicators) identify tracks having a high error probability. These pointers may be based on one or several of tape system parameters: amplitude less than a preset threshold, excessive phase shift, skew and tape speed variation and, where there is code conversion in recording and sensing, the recognition of invalid code combinations. However the advantage must be weighed against the economics of the additional structure to provide the inclusion of such facilities.